// 邻接矩阵

#pragma once

// 图的邻接矩阵存储结构
template <typename V, typename E, int M = 10>
struct AMGraph
{
    V vexs[M];          // 顶点
    E arcs[M][M];       // 邻接矩阵
    int vexnum, arcnum; //顶点和弧的数量
    bool visited[M];    //顶点的访问标志
};

// 初始化图 InitGraph(&G)
template <typename V, typename E, int M>
void InitGraph(AMGraph<V, E, M> &G)
{
    G.vexnum = G.arcnum = 0;
    // for(int i=0;i<M;i++)
    // {
    //     for(int j=0;j<M;j++)
    //     {
    //         G.arcs[i][j] = 0;
    //     }
    // }
}

// 销毁图 DestroyGraph(&G)
template <typename V, typename E, int M>
void DestroyGraph(AMGraph<V, E, M> &G)
{
    G.vexnum = G.arcnum = 0;
}

// 添加顶点 AddVertex(&G,vex)
template <typename V, typename E, int M>
int AddVertex(AMGraph<V, E, M> &G ,V vex)
{
    if (G.vexnum == M)
        throw "Too many vertexes";
    // 插入顶点数据
    int i = G.vexnum;
    G.vexs[i] = vex;
    G.vexnum++;

    // 初始化顶点相连的弧
    for(int j = 0; j < G.vexnum; j++)
    {
        G.arcs[i][j] = 0;
        G.arcs[j][i] = 0;
    }

    // 返回顶点的编号
    return i;
}

// 添加弧（边） AddArc(&G,s,t,e)
// 在图 G 中添加从顶点 s 到顶点 t 的弧及其对应的信息 e
template <typename V, typename E, int M>
void AddArc(AMGraph<V, E, M> &G, int s, int t, E e)
{
    if (s < 0 || s >= G.vexnum)
        throw "Invalid s";
    if (t < 0 || t >= G.vexnum)
        throw "Invalid t";

    G.arcs[s][t] = e;
    G.arcnum++;
}

// 从图 G 中的顶点 v 出发进行深度优先遍历图
// 从每个顶点调用 visit() 进行访问
template <typename V, typename E, int M, typename F>
void DFS(AMGraph<V, E, M> &G, int v, F visit)
{
    // 访问顶点 v
    visit(G.vexs[v]);
    G.visited[v] = true;

    // 依次从顶点 v 的未访问的临界点 w 出发深度优先搜索
    for(int w= 0;w<G.vexnum;w++)
    {
        if (G.arcs[v][w] && !G.visited[w])
        {
            DFS(G, w, visit);
        }
    }
}

// 深度有点搜索图 DFSTraverse(G,visit)
// 深度优先遍历图 G，对每个顶点调用 visit() 访问
template <typename V, typename E, int M, typename F>
void DFSTraverse(AMGraph<V, E, M> &G, F visit)
{
    // 初始化每个顶点的访问标志为未访问
    for (int v = 0; v < G.vexnum; v++)
    {
        G.visited[v] = false;
    }
    // 从每一个未访问的顶点出发进行深度优先搜索
    for (int v = 0; v < G.vexnum; v++)
    {
        if (!G.visited[v])
        {
            DFS(G, v, visit);
        }
    }
}